package sort.heapsort;

import sort.generator.ArrayGenerator;
import sort.helper.SortingHelper;

/**
 * @author XY
 * @version 1.0
 * @date 2021/12/9 15:21
 * @Description  堆排序
 */
public class HeapSort {

    private HeapSort(){

    }

    //堆排序
    public static <E extends Comparable<E>> void sort(E[] arr){
        if(arr.length<=1){
            return ;
        }
        //先将数据整理成堆的形式
        for(int i = (arr.length-2)/2; i>=0; i--){
            siftDown(arr,i,arr.length);
        }
        //将堆首与堆尾的元素交换位置
        for(int i = arr.length-1 ; i>=0 ;i--){
            swap(arr,0,i);
            //直接将堆首元素进行下沉操作即可，因为其他元素还是满足堆的性质的,下成深度为每次交换都-1
            siftDown(arr,0,i);
        }

    }

    //对 data[0,length) 所形成的最大堆中，索引k的元素执行下沉操作
    private static <E extends Comparable<E>> void siftDown(E[] arr, int k, int length) {
        while(2*k+1<length){
            //先拿到左孩子，因为一个节点如果有子节点的话一定现有左孩子
            int j = 2*k+1;
            //比较左孩子与有孩子哪个大，最后跟最大的进行比较
            if(j+1 < length && arr[j+1].compareTo(arr[j]) > 0){
                j = 2*k+2;
            }
            //如果当前元素大于孩子元素，那就说明已经符合堆的性质
            if(arr[k].compareTo(arr[j])>=0){
                break;
            }
            //否则交换位置继续比较
            swap(arr, k, j);
            k = j;
        }
    }

    private static <E extends Comparable<E>> void swap(E[] arr, int k, int j) {
        E temp = arr[k];
        arr[k] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int n = 1000000;
        Integer[] integers = ArrayGenerator.generateRandomArray(n, n);
        SortingHelper.sortTest("HeapSort",integers);
    }


}
